/*
 * @lc app=leetcode.cn id=93 lang=cpp
 *
 * [93] 复原 IP 地址
 */
#include "include.h"
// @lc code=start
class Solution {
public:    
    vector<string> restoreIpAddresses(string s) {

        int insertPosNum = 0;
        std::vector<int> insertIndex(dotNum, 0);
        
        traceBack(insertIndex, insertPosNum, s, 0, s.size()-1);

        return res;
    }
private:
    const int dotNum = 3;
    std::vector<string> res;
private:
    void traceBack(std::vector<int>& insertIndex, int insertPosNum, const std::string& s, int start, int end){
        if (insertPosNum==dotNum){
            if (checkSplitValid(start, end, s)){
                buildOneAnswer(insertIndex, s);
            }
            return;
        }
        for (int i=start;i<=end and i<start+3;i++){
            if (checkSplitValid(start, i, s)){
                insertIndex[insertPosNum] = i;
                insertPosNum += 1;
                traceBack(insertIndex, insertPosNum, s, i+1, end);
                insertPosNum -= 1;
                insertIndex[insertPosNum] = 0;
            }
        }
    }
    bool checkSplitValid(int start, int end, const std::string& s){
        int length = end - start + 1;
        if (length == 0){return false;}
        if (length > 3){return false;}
        if (s[start] == '0' and length > 1){return false;}
        int num = 0;
        int mul = 1;
        for (int pos=end;pos>=start;pos--){
            num += mul * (s[pos]-'0');
            mul *= 10;
        }
        return num <= 255;
    }
    void buildOneAnswer(const std::vector<int>& insertIndex, const std::string& s){
// printf("build %d %d %d\n", insertIndex[0], insertIndex[1], insertIndex[2]);
        std::string result;
        
        appendResult(0, insertIndex[0], s, result);
        result += ".";
        appendResult(insertIndex[0]+1, insertIndex[1], s, result);
        result += ".";
        appendResult(insertIndex[1]+1, insertIndex[2], s, result);
        result += ".";
        appendResult(insertIndex[2]+1, s.size()-1, s, result);

        res.emplace_back(result);
// printf("%s\n", result.c_str());
    }
    void appendResult(int start, int end, const std::string& s, std::string& result){
        for (int i=start;i<=end;i++){
            result += s[i];
        }
    }
};
// @lc code=end

// s = "101023"
// ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

// "25525511135"
// ["255.255.11.135","255.255.111.35"]

// 2 5 7
// 2 5 8

int main(){
    Solution test;
    auto res = test.restoreIpAddresses("101023");
    printf("-------------\n");
    for (auto& possibleResult : res){
        printf("%s \n", possibleResult.c_str());
    }
}